package com.young.vo;

import java.util.HashMap;
import java.util.Map;

public class TrieTree {
    public class TrieNode{
        public char value;
        public int isEnd; //0表示非终结 1表示终结
        public Map<Character,TrieNode>children;
        public TrieNode(char value,int isEnd){
            this.value=value;
            this.isEnd=isEnd;
            this.children=new HashMap<>();
        }
        public TrieNode(char value){
            this.value=value;
            this.isEnd=0;
            this.children=new HashMap<>();
        }
        public TrieNode(){
            this.isEnd=0;
            this.children=new HashMap<>();
        }
    }
    private TrieNode root;
    public TrieTree(){
        this.root=new TrieNode();
    }
    //插入敏感词汇
    public void insert(String str){
        if(str==null||str.length()==0){
            return ;
        }
        root=insert(root,str,0);
    }
    //判断字符串中，是否包含敏感词汇
    public boolean match(String str){
        if (str == null || "".equals(str)) {
            return false;
        }
        TrieNode temp=root;
        for(int i=0;i<str.length();i++){
            char ch=str.charAt(i);
            //获取到下一个节点
            TrieNode next = temp.children.get(ch);
            if (next==null){
                temp=root;
            }else{
                temp=next;
            }
            if (temp.isEnd==1){
                return true;
            }
        }
        return false;
    }
    //移除敏感词汇
    public void remove(String str){
        if (str == null || "".equals(str)) {
            return;
        }
        //没有该敏感词时,直接返回
        if (!match(str)){
            return;
        }
        //开始删除敏感词
        root=remove(root,str,0);
    }

    private TrieNode remove(TrieNode t,String str,int index){
        char ch=str.charAt(index);
        TrieNode child = t.children.get(ch);
        //到达最末尾
        if (index==str.length()-1){
            if (child.children.size()>0){
                //当前节点有子节点时，将标记为设置为0即可
                child.isEnd=0;
            }else{
                //否则直接删除该节点
                t.children.remove(ch);
            }
            return t;
        }
        //往下删除
        child=remove(child,str,++index);
        //回溯
        if (child.children.size()==0&&child.isEnd==1){
            //当没有节点并且isEnd==0时
            t.children.remove(ch);
        }
        return t;
    }
    private TrieNode insert(TrieNode t,String str,int index){
        char ch=str.charAt(index);
        TrieNode child = t.children.get(ch);
        if (child!=null){
            if (index==str.length()-1){
                child.isEnd=1;
                return t;
            }
            child=insert(child,str,++index);
//            t.children.put(ch,child);
            return t;
        }
        child=new TrieNode(ch);
        if (index==str.length()-1){
            child.isEnd=1;
        }else{
            child=insert(child,str,++index);
        }
        t.children.put(ch,child);
        return t;
    }

    public static void main(String[] args) {
        String[]sensitive={"华南理工","大学生","泰裤辣"};
        TrieTree trieTree=new TrieTree();
        for(int i=0;i<sensitive.length;i++){
            trieTree.insert(sensitive[i]);
        }
        System.out.println(trieTree.match("我是华南大学的学生"));
        System.out.println(trieTree.match("华北理工大学泰裤"));
        System.out.println(trieTree.match("华南理工大学"));
        System.out.println(trieTree.match("大学生"));
        System.out.println(trieTree.match("大学生泰裤辣"));
        System.out.println(trieTree.match("人之初性本善性相近习相远华南大学泰山崩于前而面不改色泰裤辣哈哈哈哈哈哈"));
        trieTree.remove("华南理工");
        System.out.println(trieTree.match("华南理工大学"));
        trieTree.remove("大学生");
        System.out.println(trieTree.match("大学生"));
        trieTree.remove("泰裤辣");
        System.out.println(trieTree.match("人之初性本善性相近习相远华南大学泰山崩于前而面不改色泰裤辣哈哈哈哈哈哈"));
    }
}
